COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00006 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}
\baselineskip 14pt
\rm
\line{\sevenrm a22.tex[154,phy] \today\hfill}

\parskip5pt
\parindent0pt
\bigskip
\noindent{\bf Exercise:} In the regular expression for the number of paths
from a node to itself in the complete graph on $n$~nodes, how many stars
are needed? (An upper bound suffices.)

\bigskip
\noindent{\bf Answer.}

$$\vcenter{\halign{$\ctr{#}$\qquad&$\ctr{#}$\qquad&$\ctr{#}$&$\ctr{#}$%
&$\ctr{#}$\quad&$\ctr{#}$\cr
&&&&&2\cr
\noalign{\bigskip}
&\epsilon\cr
0&&&1&&3\cr
\noalign{\smallskip}
&&&&&=n\cr
\noalign{\smallskip}
&&\epsilon\cr
\noalign{\bigskip}
&&&4&=n+1\cr}}$$

\bigskip\noindent
Labels initially have 0~stars. Eliminating a node other than~1 replaces
labels with $k$~stars by labels with $4k+1$ stars. Let $f(i)$ be the number
of stars when $i$~nodes (other than node~1) have been eliminated; 
$$\eqalign{f(0)&=0\,;\cr
f(i+1)&=4f(i)+1\,.\cr}$$
Adding a constant to both sides, 
$f(i+1)+c=4f(i)+1+c$;
letting $1+c=4c$, or $c=1/3$, we get:
$$\eqalign{f(i+1)+{1\over 3}&=4\biggl(f(i)+{1\over 3}\,\biggr)\,;\cr
\noalign{\smallskip}
f(i)+{1\over 3}&=4↑i\biggl(f(0)+{1\over 3}\,\biggr)\,;\cr
\noalign{\smallskip}
f(i)&={4↑i-1\over 3}\cr}$$
and after eliminating node 1, we have one more star, for $4↑i+2\over 3$
as total.

\bigskip
\noindent{\bf Exercise.}

{\bf (A)} Define an NFA for the set of strings over $\Sigma=\{a,b\}$ which 
consist of:

\disleft 30pt:: a string of $a$'s and $b$'s with the number of $b$'s
divisible by~3; then, two consecutive~$a$'s; then a string of $a$'s
and~$b$'s with an even number of~$b$'s.

\smallskip
{\bf (B)} Construct an equivalent DFA.

\smallskip
{\bf (C)} Minimize it.


\bigskip
\parindent0pt
\copyright 1984 Robert W. Floyd

First draft October 16, 1984

\bye